package 动态规划.backageQuestion;

/**
 *
 * 最大连续子数组问题
 * 最大子数组和问题是一个经典的动态规划问题，它要求找到一个数组中的一个连续子数组，使得该子数组的和最大。
 *
 * 解题思路：
 *    1.定义状态：dp[i] 表示以 nums[i] 结尾的连续子数组的最大和, dp[i]只是以num[i] 为结尾的子数组最大和，而不是任意子数组的最大和，
 *    所以使用中间变量时刻更新最大值
 *    2: 对于nums[i] ,有两种情况：
 *       与i-1子数组连续，那么dp[i] = dp[i-1]+num[i]
 *       不连续，就从从nums[i] 重新开始连续
 *    对于这两种情况，哪个值最大就取哪个
 *    dp[i] = max(dp[i-1]+nums[i],nums[i])
 *    // 最大值
 *    max = Math.max(max,dp[i])
 *    3: 初始化：dp[0] = nums[0]
 *
 * @Author lf
 * @Date 3/21/2024
 */
public class MaxChildArrays {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0){
            throw new IllegalArgumentException("Array is empty or null");
        }
        int max = nums[0]; // 第一个默认最大值
        int currentMax = nums[0]; // 当前最大值
        for (int i = 1; i <nums.length ; i++) {
            //  dp[i] = max(dp[i-1]+nums[i],nums[i])
            currentMax = Math.max(currentMax+nums[i],nums[i]);
            // 然后更新最大值
            max = Math.max(max,currentMax);
        }
        return max;
    }

    public static void main(String[] args) {
        MaxChildArrays solution = new MaxChildArrays();
        int[] nums = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println("Maximum Subarray Sum: " + solution.maxSubArray(nums));
    }
}
